home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 7 / Amiga Format AFCD07 (Dec 1996, Issue 91).iso / serious / shareware / programming / ixemul-complete / ixemul / library / buddy-alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-08  |  9.7 KB  |  357 lines
  1. /*
  2.  *  This file is part of ixemul.library for the Amiga.
  3.  *  Copyright (C) 1991, 1992  Markus M. Wild
  4.  *
  5.  *  This library is free software; you can redistribute it and/or
  6.  *  modify it under the terms of the GNU Library General Public
  7.  *  License as published by the Free Software Foundation; either
  8.  *  version 2 of the License, or (at your option) any later version.
  9.  *
  10.  *  This library is distributed in the hope that it will be useful,
  11.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.  *  Library General Public License for more details.
  14.  *
  15.  *  You should have received a copy of the GNU Library General Public
  16.  *  License along with this library; if not, write to the Free
  17.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  *
  19.  *  $Id: buddy-alloc.c,v 1.4 1994/06/19 15:02:51 rluebbert Exp $
  20.  *
  21.  *  $Log: buddy-alloc.c,v $
  22.  *  Revision 1.4  1994/06/19  15:02:51  rluebbert
  23.  *  *** empty log message ***
  24.  *
  25.  *  Revision 1.2  1992/09/14  01:40:24  mwild
  26.  *  change from using aligned blocks (obtained thru an AllocMem/FreeMem/AllocAbs
  27.  *  hack) to using non-aligned blocks. The price for this is an additional
  28.  *  field in every allocated block.
  29.  *
  30.  *  In the same run, change Forbid/Permit into Semaphore locking.
  31.  *
  32.  *  Revision 1.1  1992/05/22  01:42:33  mwild
  33.  *  Initial revision
  34.  *
  35.  */
  36. #define _KERNEL
  37. #include "ixemul.h"
  38. #include "kprintf.h"
  39. #include <exec/memory.h>
  40. #include <stddef.h>
  41.  
  42. #ifdef DEBUG_VERSION
  43. #define P(arg) KPRINTF (arg)
  44. #define DP(arg) KPRINTF (arg)
  45. #else
  46. #define P(arg)
  47. #define DP(arg)
  48. #endif
  49.  
  50.  
  51. /* this provides a straight replacement for AllocMem() and FreeMem().
  52.    Being this, it does *not* remember the size of allocation, the
  53.    clients have to do this instead. */
  54.  
  55. /* NOTE: currently only two pools are supported, MEMF_PUBLIC and
  56.          ! MEMF_PUBLIC. No MEMF_CHIP pools are needed by the library
  57.          and are thus not supported */
  58.  
  59.  
  60. /* TUNING: The two parameters that can be adjusted to fine tune
  61.            allocation strategy are MAXSIZE and BUDDY_LIMIT. By setting
  62.            MAXSIZE larger than BUDDY_LIMIT results in less Exec
  63.            overhead, since blocks stay longer in the buddy system.
  64.            Setting MAXSIZE==BUDDY_LIMIT sets memory usage to the
  65.            minimum, at the cost of more Exec calls. */
  66.  
  67.  
  68. /* no request for memory can be lower than this */
  69. #define MINLOG2        4
  70. #define MINSIZE        (1 << MINLOG2)
  71.  
  72. /* this is the size the buddy system gets memory pieces from Exec */
  73. #define MAXLOG2        15    /* get 32K chunks */
  74. #define MAXSIZE        (1 << MAXLOG2)
  75.  
  76. /* this is the limit for b_alloc to go straight to Exec */
  77. #define BUDDY_LIMIT    (1 << (MAXLOG2 - 5))    /* but serve only upto 1K */
  78.  
  79. #define PRIVATE_POOL    0
  80. #define PUBLIC_POOL    1
  81. #define NUMPOOLS    2    /* public and !public */
  82. /* attention: don't go larger than 3 pools, or you'll have to change the
  83.               encoding in free_block (only 2 bits for now) */
  84.  
  85. struct free_list {
  86.   u_int  exec_attr;
  87.   struct SignalSemaphore sem;
  88.   struct MinList buckets[MAXLOG2 - MINLOG2];
  89. } free_list[NUMPOOLS] = { { 0, }, { MEMF_PUBLIC, } };
  90.  
  91.  
  92. struct free_block {
  93.   /* to make the smallest allocatable block 16, and not 32 byte, stuff both
  94.      the freelist information and the exec-block address into one long. */
  95.   u_int    pool:2,        /* 0: block is free, > 0: POOL + 1 */
  96.       exec_block:30;    /* shift left twice to get the real address */
  97.  
  98.   /* from here on, fields only exist while the block is on the free list.
  99.      The application sees a block as a chunk of memory starting at &next */
  100.   struct free_block *next, *prev;    /* min-node compatible */
  101.   int index;
  102. };
  103.  
  104.  
  105. void
  106. init_buddy (void)
  107. {
  108.   int i, l; 
  109.  
  110.   /* don't want such a nightmare of bug-hunt any more... */
  111.   if (sizeof (struct free_block) > MINSIZE)
  112.     {
  113.       ix_panic ("buddy-system: MINSIZE/MINLOG2 too small, increase!");
  114.       Wait (0);
  115.     }
  116.  
  117.   for (l = 0; l < NUMPOOLS; l++)
  118.     {
  119.       for (i = 0; i < MAXLOG2 - MINLOG2; i++)
  120.     NewList ((struct List *) &free_list[l].buckets[i]);
  121.       InitSemaphore (&free_list[l].sem);
  122.     }
  123. }
  124.  
  125. static inline struct free_block *
  126. unlink_block (u_int free_pool, u_char ind, void *block)
  127. {
  128.   struct free_block *fb = (struct free_block *) block;
  129.   struct free_list *fl = free_list + free_pool;
  130.  
  131.   if (! fb)
  132.     {
  133.       fb = (struct free_block *) RemHead ((struct List *) &fl->buckets[ind]);
  134.       if (fb)
  135.     {
  136.       fb = (struct free_block *) ((int)fb - offsetof (struct free_block, next));
  137.       fb->pool = free_pool + 1;
  138.       P(("    unlink_block (%s, %ld) == $%lx\n", 
  139.          free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
  140.  
  141.     }
  142.     }
  143.   else
  144.     {
  145.       P(("    unlink_block (%s, %ld, $%lx)\n", 
  146.      free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
  147.  
  148.       fb->pool = free_pool + 1;
  149.       Remove ((struct Node *) &fb->next);
  150.     }
  151.  
  152.   return fb;
  153. }
  154.  
  155. static void inline
  156. link_block (u_int free_pool, u_char ind, void *block)
  157. {
  158.   struct free_block *fb = (struct free_block *) block;
  159.   struct free_list *fl = free_list + free_pool;
  160.  
  161.   P(("    link_block (%s, %ld, $%lx)\n", 
  162.      free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), ind, fb));
  163.  
  164.   fb->pool = 0;    /* we're on the freelist of this pool */
  165.   fb->index = ind; /* and of this size */
  166.   AddHead ((struct List *) &fl->buckets[ind], (struct Node *) &fb->next);
  167. }
  168.  
  169. /* this is a very special log2() function that knows the upper bound
  170.    of its argument, and also automatically rounds to the next upper
  171.    power of two */
  172.  
  173. static inline int const
  174. log2 (int size)
  175. {
  176.   int pow = MAXLOG2;
  177.   int lower_bound = 1 << (MAXLOG2 - 1);
  178.  
  179.   for (;;)
  180.     {
  181.       if (size > lower_bound)
  182.         return pow;
  183.  
  184.       lower_bound >>= 1;
  185.       pow--;
  186.     }
  187. }
  188.  
  189.  
  190. static inline struct free_block *
  191. get_block (u_int free_pool, u_char index)
  192. {
  193.   struct free_block *fb, *buddy;
  194.   struct free_list *fl = free_list + free_pool;
  195.  
  196.   P(("  get_block (%s, %ld)\n", 
  197.      free_pool == PRIVATE_POOL ? "PRIVATE" : (free_pool == PUBLIC_POOL ? "PUBLIC" : "BOGOUS"), index, fb));
  198.  
  199.   if (index == (MAXLOG2 - MINLOG2))
  200.     {
  201.       fb = (struct free_block *) AllocMem (MAXSIZE, fl->exec_attr);
  202.       if (! fb)
  203.         return 0;
  204.  
  205.       fb->exec_block = (int)fb >> 2; /* buddies are relative to this base address */
  206.       fb->pool = free_pool + 1; /* not free */
  207.  
  208.       return fb;
  209.     }
  210.   else 
  211.     {
  212.       if ((fb = unlink_block (free_pool, index, 0)))
  213.         return fb;
  214.     }
  215.  
  216.  
  217.   fb = get_block (free_pool, index + 1);
  218.  
  219.   if (fb)
  220.     {
  221.       /* when splitting a block, we always free the upper buddy. So
  222.          we can just add the size, instead of or'ing the offset to the
  223.          Exec memory block */
  224.       buddy = (struct free_block *)((int)fb + (1 << (index + MINLOG2)));
  225.  
  226.       buddy->exec_block = fb->exec_block;
  227.  
  228.       link_block (free_pool, index, buddy);
  229.     }
  230.  
  231.   return fb;
  232. }
  233.  
  234.  
  235. static inline void
  236. free_block (u_int free_pool, u_char index, struct free_block *fb)
  237. {
  238.   struct free_block *buddy;
  239.  
  240.   buddy = (struct free_block *)
  241.       ((((int)fb - (fb->exec_block<<2)) ^ (1 << (index + MINLOG2)))
  242.        + (fb->exec_block<<2));
  243.  
  244.   if (index == (MAXLOG2 - MINLOG2))
  245.     {
  246.  
  247.       FreeMem (fb, MAXSIZE);
  248.       return;
  249.     }
  250.   else if (buddy->pool || buddy->index != index)
  251.     {
  252.       /* too bad, buddy is not on freelist or of wrong size */
  253.       link_block (free_pool, index, fb);
  254.       return;
  255.     }
  256.  
  257.   /* reserve the buddy, then recombine both */
  258.   unlink_block (free_pool, index, buddy);
  259.  
  260.   /* since the buddy is free as well, recombine both blocks
  261.      and free the twice as large block */
  262.   free_block (free_pool, index + 1, fb < buddy ? fb : buddy);
  263. }
  264.  
  265.  
  266. void *
  267. b_alloc (int size, unsigned pool)
  268. {
  269.   u_char bucket;
  270.   int omask;
  271.   struct free_block *block;
  272.   struct free_list *fl = free_list + pool;
  273.  
  274.   if (size < 0)    /* Ridiculous size */
  275.     return 0;
  276.   if (size < MINSIZE)
  277.     size = MINSIZE;
  278.  
  279.   /* the additional bytes are needed for the freelist pointer at
  280.      the beginning of each block in use and the base block originally
  281.      obtained from Exec. */
  282.  
  283.   if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
  284.     return AllocMem (size, pool == PUBLIC_POOL ? MEMF_PUBLIC : 0);
  285.  
  286.   size += offsetof (struct free_block, next);
  287.  
  288.   bucket = log2 (size) - MINLOG2;
  289.  
  290.   /* have to differentiate between PUBLIC and PRIVATE memory here, sigh. 
  291.      PRIVATE memory can safely be accessed by using a semaphore, PUBLIC
  292.      memory however is allocated and free'd inside Forbid(), and using a
  293.      semaphore there would possibly break a Forbid..
  294.      Note: this is safe for use in GigaMem, as GigaMem only uses non-PUBLIC
  295.        memory, if you don't fiddle with attribute masks.. */
  296.   if (pool == PRIVATE_POOL)
  297.   {
  298.     omask = syscall (SYS_sigsetmask, ~0);
  299.     ObtainSemaphore (&fl->sem);
  300.     block = get_block (pool, bucket);
  301.     ReleaseSemaphore (&fl->sem);
  302.     syscall (SYS_sigsetmask, omask);
  303.   }
  304.   else
  305.   {
  306.     Forbid();
  307.     block = get_block (pool, bucket);
  308.     Permit();
  309.   }
  310.  
  311.   if (block)
  312.     return (void *) & block->next;
  313.   else
  314.     return block;
  315. }
  316.  
  317.  
  318. void
  319. b_free (void *mem, int size)
  320. {
  321.   u_char bucket;
  322.   struct free_list *fl;
  323.   struct free_block *fb;
  324.   int free_pool, omask;
  325.  
  326.   if (size < MINSIZE)
  327.     size = MINSIZE;
  328.     
  329.   if (size >= BUDDY_LIMIT - offsetof (struct free_block, next))
  330.     {
  331.       FreeMem (mem, size);
  332.       return;
  333.     }
  334.  
  335.   size += offsetof (struct free_block, next);
  336.  
  337.   bucket = log2 (size) - MINLOG2;
  338.   fb = (struct free_block *) ((int)mem - offsetof (struct free_block, next));
  339.   free_pool = fb->pool - 1;
  340.   fl = free_list + free_pool;
  341.  
  342.   if (free_pool == PRIVATE_POOL)
  343.   {
  344.     omask = syscall (SYS_sigsetmask, ~0);
  345.     ObtainSemaphore (&fl->sem);
  346.     free_block (free_pool, bucket, fb);
  347.     ReleaseSemaphore (&fl->sem);
  348.     syscall (SYS_sigsetmask, omask);
  349.   }
  350.   else
  351.   {
  352.     Forbid();
  353.     free_block (free_pool, bucket, fb);
  354.     Permit();
  355.   }
  356. }
  357.